Năm 1863, nhóm Shieikan mà đứng đầu là Kondo Isami gia nhập Roshigumi (浪士組 Lãng sĩ tổ) do Kiyokawa Hachiro, một chí sĩ phiên Shonai thành lập, nhằm mục đích hộ tống Tướng quân (Shogun) Tokugawa Iemochi lên kinh thành Kyoto. Nhưng sau vì phát hiện âm mưu thực sự của Kiyokawa là gầy dựng lực lượng đảo Mạc, nên phần lớn các thành viên quyết định rời khỏi Roshigumi và trở về Edo, thành lập Shinchogumi (新徴組 Tân Trưng Tổ) ở Edo mà thủ lãnh là Okita Rintaro, anh rể Okita Soji (Đội trưởng đội 1 Shinsengumi), là một lực lượng cảnh sát tá Mạc (Phò trợ Mạc phủ) có quy chế và nhiệm vụ tương tự Shinsengumi, thường được xem là anh em với Shinsengumi. Những người và các nhóm còn lại như nhóm Kondo và nhóm Serizawa tuy cũng phản đối và rời tổ chức nhưng chủ trương cũng như vì mục đích bảo vệ và phục vụ Tướng quân nên tình nguyện ở lại kinh thành. Sau cùng, nhóm Kondo, nhóm Serizawa và nhóm Tonochi quyết định gửi thỉnh nguyện đơn thành lập một tổ chức mới, Mibu roshigumi (壬生浪士組 Nhâm Sanh lãng sĩ tổ, tiền thân của Shinsengumi) vì nhóm đóng bản doanh ở làng Mibu, sống trong dinh thự Yagi và dinh thự Maekawa của nhà Yagi. Nhưng do mâu thuẫn nội bộ mà nhóm Kondo cùng nhóm Serizawa quyết định ám sát nhóm Tonochi. Kondo và Serizawa Kamo, Niimi Nishiki (Dưỡng đệ, tức em nuôi của Serizawa) cùng trở thành những lãnh đạo của nhóm, Hijikata và Yamanami là hai Phó cục trưởng, nhưng sau vì vài lý do nội bộ mà Niimi Nishiki bị giáng chức thành Phó cục trưởng. Nhóm Miburoshi phụng sự Mạc Phủ trong vai trò lực lượng cảnh sát đặc biệt ở Kyoto dưới quyền Matsudaira Katamori, lãnh chúa phiên Aizu. Tuy nhiên, theo nhiều sử gia, sau khi đổi tên thành Shinsengumi, nhóm còn là một biệt đội tử thần, chuyên thực thi các phi vụ bắt bớ cùng ám sát những người có tư tưởng đảo Mạc, trong đó có các Ishin shishi (維新志士 Duy Tân chí sĩ, gồm nhiều chính trị gia và các sát thủ của họ, thuộc phe đối địch, chuyên ám sát các yếu nhân của Mạc Phủ). Vì lý do này mà Kondo bị xử trảm với tội danh ám sát Sakamoto Ryoma, một chí sĩ huyền thoại của phiên Tosa, dù rằng sự việc này là án oan cho cả Kondo lẫn nhóm Shinsengumi.

Tuy trực thuộc phiên Aizu và được chính quyền tài trợ nhưng Shinsengumi đã vấp phải không ít khó khăn liên quan đến vấn đề kinh phí hoạt động. Thiếu thốn nên nhóm Serizawa bắt đầu gây sự, rượu chè và cưỡng đoạt tiền bạc, khiến danh tiếng bị ô uế và nhóm bị gọi là "Sói Mibu" (Miburo 壬生狼 Nhâm Sanh lang, đồng âm khác nghĩa với Miburo 壬生浪 Nhâm Sanh lãng). Toshizo đã tìm đủ chứng cứ buộc tội Niimi và lệnh cho ông này phải mổ bụng. Một tuần sau, Serizawa cùng nhân tình và các môn đệ bị ám sát. Phần lớn sử liệu cho rằng chính phiên chủ Matsudaira đã lệnh Kondo bí mật thanh trừng nhóm Serizawa, Kondo và Toshizo phải nhận lệnh, và Toshizo đảm nhận nhiệm vụ với cái cớ là Serizawa chết do bị bọn cướp hoặc nhóm sát thủ phiên Choshu ám hại, cũng theo sử thuyết được đồng thuận cao nhất thông qua lời kể của người con trai nhà Yagi, Tamesaburo - Một chứng nhân, tuy còn nhỏ tuổi vào thời điểm xảy ra vụ ám sát và lúc ấy trời mưa khá to, có thể không nhìn rõ mặt - thì ngoài Toshizo, trong nhóm ám sát còn có Okita Soji, Yamanami Keisuke và Harada Sanosuke. Kondo trở thành người lãnh đạo duy nhất của nhóm, cùng hai Phó cục trưởng là Yamanami và Toshizo (Sau vì Yamanami chuyển sang chức vụ "Tổng trưởng", nên chỉ còn Phó cục trưởng Hijikata).

Năm 1864, danh tiếng Shinsengumi vang dội khắp Nhật Bản khi khám phá và trấn áp thành công ý đồ phóng hoả kinh thành của nhóm phản loạn trong sự kiện Ikedaya (Ikedaya jiken 池田屋事件 Trì Điền Ốc sự kiện). Trước đó, Hijikata đã ép được một thành viên phản loạn phải khai ra toàn bộ kế hoạch, bằng cách treo mắt cá chân, bẻ cổ tay, đóng những cây đinh dài đến 5 inch vào gót chân, đặt nến đang cháy lên trên lỗ, để sáp nóng chảy nhỏ giọt xuống bắp chân, có như vậy mới bắt ép đối phương mở miệng, dù vẫn còn rất nhiều tranh cãi xung quanh việc Hijikata có trực tiếp liên quan đến phương cách tàn bạo này không.

Nhóm phát triển lên quy mô 140 người, sau nữa là hơn 300, gồm nhiều tầng lớp, từ samurai, nông dân đến các nhà buôn mà kế sinh nhai của họ bị đe doạ nếu Mạc Phủ sụp đổ. Do số lượng thành viên tăng nhanh, quy mô dần mở rộng, nên để hợp thức hoá thành một tổ chức cảnh sát thật sự, cũng như siết chặt kỷ cương, nêu cao tinh thần võ sĩ đạo, Toshizo được xem là người đã đặt ra những nội quy, quân pháp vô cùng hà khắc. Đối với những kẻ bỏ trốn hoặc phản bội, buộc phải seppuku, chưa kể là tham nhũng - biển thủ công quỹ, mờ ám trong các công vụ, và trong chiến trận mà tỏ ra hèn nhát không tham chiến hoặc bỏ chạy, tất đều xử mổ bụng, không có trường hợp ngoại lệ, kể cả tình riêng. Sự khắc nghiệt này đã xảy ra với Yamanami khi ông từng bỏ trốn khỏi Shinsengumi năm 1865 trước khi tự thú cùng năm (Yamanami là người thuộc nhóm Shieikan của Kondo, và là một trong số ít bạn hữu thân thiết, tâm đắc của Toshizo thời trước khi đến Kyoto). Nhưng nhờ vậy, Shinsengumi trở thành tổ chức cảnh sát thực thụ, là lực lượng thiện chiến nhất của Mạc Phủ, với hàng trăm tay kiếm chuyên nghiệp giết người không gớm tay, ý chí chiến đấu và tinh thần kỷ luật cao, Shinsengumi thật sự trở thành nỗi kinh hoàng cho kẻ thù, không những thế, ngay cả quân Mạc Phủ cũng phải e dè, sợ hãi và kiêng nể. Nhờ Toshizo, Shinsengumi trở thành tấm gương anh dũng cho quân đội Mạc Phủ, trong khoảng thời gian tồn tại ngắn ngủi, tánh anh hùng bất khuất mang đậm tinh thần võ sĩ đạo của họ đã in sâu vào tâm trí và được ngưỡng mộ, tưởng nhớ bởi phần lớn tầng lớp thị dân.

Cùng với những thành viên khác của Shinsengumi, Toshizo trở thành Hatamoto năm 1867.[1] Ông được thăng cấp Yoriai đầu năm 1868.[2]